package com.ma.dp.a01;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Solution10
 * @Author: mayongqiang
 * @DATE 2022/4/15 15:01
 * @Description: 正则表达式匹配
 */
public class Solution10 {
    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a*"));
    }

    static Map<String, Boolean> memo = new HashMap<>();

    public static boolean isMatch(String s, String p) {

        // dp(i,j) 表示 s(i..) 匹配 p(j..) 的结果  布尔值
        return dp(s, 0, p, 0);
    }

    private static boolean dp(String s, int i, String p, int j) {
        int m = s.length(), n = p.length();
        if (j == n) {
            return i == m;
        }
        if (i == m) {
            if ((n - j) % 2 == 1) {
                return false;
            }
            for (; j + 1 < n; j += 2) {
                if (p.charAt(j + 1) != '*') {
                    return false;
                }
            }
            return true;
        }

        String key = i + "," + j;
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        boolean res = false;
        boolean b = j < n - 1 && p.charAt(j + 1) == '*';
        if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {// 1、当前匹配 i==j/j==.
            if (b) {     // 1.1 遇到x*  j+1=*
                // 两种情况，匹配0次x   匹配多次x
                res = dp(s, i + 1, p, j) ||
                        dp(s, i, p, j + 2);
            } else {                                                // 1.2 没有* 全部后移
                res = dp(s, i + 1, p, j + 1);
            }
        } else {    //2.当前不能匹配
            if (b) {  // 2.1 遇到x*
                //只能跳过 匹配0次x
                res = dp(s, i, p, j + 2);
            } else {
                return false;
            }
        }
        memo.put(key,res);
        return res;
    }
    /*
    给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
        '.' 匹配任意单个字符
        '*' 匹配零个或多个前面的那一个元素
        所谓匹配，是要涵盖整个字符串s的，而不是部分字符串
     */
}
